#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

BinaryTreeNode* findNextNode(BinaryTreeNode* root, BinaryTreeNode* find_node) {
  stack<BinaryTreeNode*> help_stack;
  BinaryTreeNode* cur_node = root;
  bool find = false;
  while (cur_node || !help_stack.empty()) {
    while (cur_node) {
      help_stack.push(cur_node);
      cur_node = cur_node->left;
    }
    cur_node = help_stack.top();
    help_stack.pop();
    if (find) {
      return cur_node;
    }
    if (cur_node == find_node) {
      find = true;
    }
    cur_node = cur_node->right;
  }
  return nullptr;
}

BinaryTreeNode* findNextNode1(BinaryTreeNode* root, BinaryTreeNode* find_node) {
  auto cur_node = root;
  BinaryTreeNode* next_node = nullptr;
  while (cur_node) {
    if (cur_node->value > find_node->value) {
      next_node = cur_node;
      cur_node = cur_node->left;
    } else {
      cur_node = cur_node->right;
    }
  }
  return next_node;
}

int main() {
  vector<int> vec = {8, 6, 10, 5, 7, 9, 11};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  PrintBinaryTree(root);

  auto ret = findNextNode(root, root);
  cout << ret->value << endl;

  auto ret1 = findNextNode1(root, root);
  cout << ret1->value << endl;

  return 0;
}
